import java.util.*;

/**
 * @program: LeetCode
 * @ClassName Num049_nthUglyNumber
 * @description: LeetCode : 剑指 Offer 49. 丑数
 * @author: WXY
 * @create: 2022-12-09 18:28
 * @Version 1.0
 **/


public class Num049_nthUglyNumber {
    public static int nthUglyNumber(int n) {
        TreeSet<Long> set = new TreeSet<>();
        set.add(1L);
        long temp = Integer.MAX_VALUE;
        while (n != 0) {
            n--;
            temp = set.pollFirst();
            set.add(temp * 2);
            set.add(temp * 3);
            set.add(temp * 5);
        }
        return (int) temp;
    }

    public static void main(String[] args) {
        int num = nthUglyNumber(1047);
        System.out.println(num);
    }
}
